import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree {
    public static class BTNode{
        BTNode left;
        BTNode right;
        int value;
        BTNode(int value){
            this.value = value;
        }
    }
    private BTNode root;
    public void createBinaryTree(){
        BTNode node1 = new BTNode(1);
        BTNode node2 = new BTNode(2);
        BTNode node3 = new BTNode(3);
        BTNode node4 = new BTNode(4);
        BTNode node5 = new BTNode(5);
        BTNode node6 = new BTNode(6);
        root = node1;
        node1.left = node2;
        node2.left = node3;
        node1.right = node4;
        node4.left = node5;
        node5.right = node6;
    }
    public void preorder(BTNode root){
        if(root == null )return ;
        System.out.println(root.value);
        preorder(root.left);
        preorder(root.right);
    }
    public void preOrder(BTNode root) {
        if(root == null){
            return ;
        }
        Stack<BTNode> stack = new Stack<>();
        BTNode cur = root;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                System.out.println(cur.value);
                cur = cur.left;
            }
            BTNode top = stack.pop();
            cur = top.right;
        }
    }
    //层序遍历
    void levelOrder(BTNode root) {
        if(root == null) {
            return;
        }
        Queue<BTNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            BTNode cur = queue.poll();
            System.out.print(cur.value+" ");

            if(cur.left != null) {
                queue.offer(cur.left);
            }
            if(cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

}
